/**
 * 冒泡排序
 *
 * 算法思想
 * 1、冒泡排序每次操作相邻的两个数，进行大小比较，看是否满足大小关系要求
 * 2、不满足就互换位置
 * 3、一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作
 * 4、优化 当某次冒泡没有数据产生交换时，说明数据以及达到有序，可以结束排序。例如数据4，5，6，3，2，1 四次排序即可完成排序
 * 时间复杂度：最好时间复杂度O(n) 最坏时间复杂度O(n^2)
 */
const sortArr: number[] = [4, 5, 6, 3, 2, 1]

function BubbleSort(arr: number[]) {
  const len: number = arr.length
  if (len <= 0) return
  for (let i = 0; i < len; i++) {
    // 是否已完成排序
    let flag: boolean = false
    for (let j = 0; j < len - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = temp
        // 有数据交换
        flag = true
      }
    }
    // 没有数据交换，结束循环
    if (!flag) break
  }
  return arr
}

console.log('冒泡排序：')
console.log(BubbleSort(sortArr))

/**
 * 插入排序
 *
 * 算法思想
 * 1、数据分为有序和无序区。初始已排序区只有数组第一个元素
 * 2、取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。
 * 3、重复这个过程，直到未排序区间中元素为空，算法结束
 * 时间复杂度：最好时间复杂度O(n) 最坏时间复杂度O(n^2)
 */
function InsertSort(arr: number[]) {
  const len: number = arr.length
  if (len <= 0) return
  for (let i = 1; i < len; i++) {
    let j = i - 1
    const temp: number = arr[i]
    // 查找插入的位置
    for (; j >= 0; j--) {
      if (arr[j] > temp) {
        // 数据移动
        arr[j + 1] = arr[j]
      } else {
        break
      }
      arr[j + 1] = temp // 插入数据
    }
  }
}

console.log('插入排序：')
console.log(BubbleSort(sortArr))

/**
 * 选择排序
 * 算法思想
 * 1、类似插入排序，分为有序和无序区
 * 2、选择排序每次会从未排序区间找出最小元素，放到已排序区间末尾
 * 最好最坏复杂度都为O(n^2)
 */
function selectSort(arr: number[]) {
  const len: number = arr.length
  if (len <= 0) return
  for (let i = 0; i < len - 1; i++) {
    let minIndex = i
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j // 找到整个数组的最小值
      }
    }
    const temp = arr[i]
    arr[i] = arr[minIndex]
    arr[minIndex] = temp
  }
  return arr
}

console.log('选择排序：')
console.log(BubbleSort(sortArr))
// 时间复杂度为O(n²)
